%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Recall that Fibonacci numbers are defined by the recurrence $F(n)=F(n-1)+F(n-2)$, with initial conditions $F(0)=0$ and $F(1)=1$. Computing the $nth$ Fibonacci number easily done in $n-1$ addictions. However, we can use divide-and-conquer techniques to compute the $nth$ Fibonacci number with $\Theta(\log n)$ arithmetic operations. Derive such an algorithm.\\

The Fibonacci numbers are defined by the following recurrence:

\[ 
\left\lbrace \begin{array}{c}
F_{n}=F_{n-1}+F_{n-2} \\ \\
F_{0} = 0 \\ \\
F_{1} = 1 \end{array} \right. \]

Let's transform this recurrence into a linear equation system

\[ 
\left\lbrace \begin{array}{c}
F_{n+1}=F_{n-1}+F_{n} \\ \\
F_{n}=F_{n} 
\end{array} \right. \]

This is equal to

\[ 
\left\lbrace \begin{array}{c}
F_{n} =0F_{n-1}+1F_{n} \\ \\
F_{n+1}=1F_{n-1}+1F_{n} 
\end{array} \right. \]

Matrix form

\[
\left( {\begin{array}{c}
 F_{n} \\
 F_{n+1} \\
 \end{array} } \right) 
 =
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{c}
 F_{n-1} \\
 F_{n} \\
 \end{array} } \right)
\]

Because we know $F_{0}$ and $F_{1}$

\[
\left( {\begin{array}{c}
 F_{1} \\
 F_{2} \\
 \end{array} } \right) 
 =
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{c}
 0 \\
 1 \\
 \end{array} } \right)
\] \\

\[
\left( {\begin{array}{c}
 F_{2} \\
 F_{3} \\
 \end{array} } \right) 
 =
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{c}
 F_{1} \\
 F_{2} \\
 \end{array} } \right)
 =
 \left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{c}
 0 \\
 1 \\
 \end{array} } \right)
\]

Repeating this over and over

\[
\left( {\begin{array}{c}
 F_{n} \\
 F_{n+1} \\
 \end{array} } \right) 
 =
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)^n
 *
 \left( {\begin{array}{c}
 0 \\
 1 \\
 \end{array} } \right)
\] \\

Although we need to simplify more this expression. Looking at the matrix of the coefficients

\[
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
\]

This expression equals to the first values of the Fibonacci numbers

\[
Q
=
\left( {\begin{array}{cc}
 F_{0} & F_{1}  \\
 F_{1} & F_{2}  \\
 \end{array} } \right)
=
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
\]

Let's use the same iteration as in the linear system and multiply by the matrix $A$ to get the subsequent set of Fibonacci numbers:

\[
Q^2
=
\left( {\begin{array}{cc}
 F_{1} & F_{2}  \\
 F_{2} & F_{3}  \\
 \end{array} } \right)
=
\left( {\begin{array}{cc}
 F_{0} & F_{1}  \\
 F_{1} & F_{2}  \\
 \end{array} } \right)
*
\left( {\begin{array}{cc}
 F_{0} & F_{1}  \\
 F_{1} & F_{2}  \\
 \end{array} } \right)
=
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)^2
 =
 \left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 *
 \left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)
 =
 \left( {\begin{array}{cc}
 1 & 1  \\
 1 & 2  \\
 \end{array} } \right)
\]

Actually this holds. Then, we have the intuition that:

\[
Q^n
=
\left( {\begin{array}{cc}
 F_{n-1} & F_{n}  \\
 F_{n} & F_{n+1}  \\
 \end{array} } \right)
=
\left( {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
 \end{array} } \right)^n
\]

Let's prove this by induction

\begin{center}
BASE (n=1)
\end{center}

\[
Q =
\left[ {\begin{array}{cc}
 F_{0} & F_{1}  \\
 F_{1} & F_{2}  \\
\end{array} } \right]
=
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]
\]\\
$F_{0}=0; F_{1}=1; F_{2}=1;$ This is correct.

\begin{center}
STEP (n+1)
\end{center}

Let's assume that the relation holds for $n$

\[
Q^n =
\left[ {\begin{array}{cc}
 F_{n-1} & F_{n}  \\
 F_{n} & F_{n+1}  \\
\end{array} } \right]
=
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]^n
\]\\

Let's see for $n+1$

\[
Q^{n+1} =
\left[ {\begin{array}{cc}
 F_{n} & F_{n+1}  \\
 F_{n+1} & F_{n+2}  \\
\end{array} } \right]
=
\left[ {\begin{array}{cc}
 F_{n-1} & F_{n}  \\
 F_{n} & F_{n+1}  \\
\end{array} } \right]
*
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]
=
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]^n
*
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]
=
\left[ {\begin{array}{cc}
 0 & 1  \\
 1 & 1  \\
\end{array} } \right]^{n+1}
\]\\

This also holds for $n+1$ so the equivalence is correct.\\

We know that for calculating the exponential of a number we can use recursive squaring which has a run-time complexity of $\Theta( \log n )$. The recursive squaring algorithm is the following:\\

\[ 
x^{n} =
\left\lbrace \begin{array}{c}
1, n=1 \\ \\
(x^{n/2})^2, \textrm{n is even} \\ \\
x(x^{(n-1)/2})^2, \textrm{n is odd} \end{array} \right. \]

The final algorithm fill look like this:

\begin{lstlisting}
fibonnaci (integer n){

  if (n == 1){
    return Matrix[ 0 1 ; 1 1 ]; O(1)
  }
  
  if (n is even){
    y = fibonacci ( n / 2 ); 
    
    return y * y; -> T(n)=T(n/2)+O(1) 
  }  
  
  if (n is odd){
    y = fibonacci ( (n - 1)/2 )
    
    return y * Matrix[ 0 1 ; 1 1 ]; -> T(n)=T((n-1)/2)+O(1)>= T(n/2)+O(1)
  }
  
}
\end{lstlisting}

The algorithm can be expressed like this:

$T(n)=T(n/2)+O(1)$\\

By the Master Theorem we can easily conclude that this algorithm has a run-time complexity of $\Theta(log n)$. Since the number of arithmetic operations in a multiplication of two square matrices is constant the complexity of this algorithm is still $\Theta(log n)$ in the number of arithmetic operations.